#!/usr/bin/env python
"""
Module automaton
"""
###############################################################################

class StateError(Exception):
    pass

###############################################################################

class TransitionError(Exception):
    pass

###############################################################################

class AutomatonError(Exception):
    pass

###############################################################################

class DFAError(Exception):
    pass

###############################################################################

class State(object):
    """class State
    """
    def __init__(self, name, final=False, initial=False):
        """Initialize a state
        """
        self._name     = name    # string
        self._final    = final   # bool
        self._initial  = initial # bool
        self._outTrans = list()  # [Transitions starting with current state,]
        self._inTrans  = list()  # [Transitions ending with current state,  ]
        self._data     = None    # Additional data

    def isInitial(self):
        """Is initial state
        """
        return self._initial

    def isFinal(self):
        """Is final state
        """
        return self._final
       
    def setInitial(self, isInitial=False):
        """Set initial
        """
        self._initial = isInitial
    
    def setFinal(self, isFinal=False):
        """Set Final
        """
        self._final = isFinal    
    
    def getName(self):
        """Return name of the state
        """
        return self._name
    
    def addOutTransition(self, transition):
        """Add one transition starting with current state 
        """
        self._outTrans.append(transition)
      
    def addInTransition(self, transition):
        """Add one transition ending with current state
        """
        self._inTrans.append(transition) 
        
    def getOutTransition(self, label=None):
        """Return list of out transition(s)
        """
        outTrans = []
        if label == None:
            return self._outTrans
        else:
            for t in self._outTrans:
                if label == t.getLabel():
                    outTrans.append(t)
        
        return outTrans
        
    def getInTransition(self, label=None):
        """Return list of in transitions(s)
        """
        inTrans = []
        if label == None:
            return self._inTrans
        else:
            for t in self._inTrans:
                if label == t.getLabel():
                    inTrans.append(t)
                    
        return inTrans

    def setData(self, key, value):
        """Assigns additional data to the state
        """
        if self._data is None:
            self._data = {}
        self._data[key] = value
        
    def getData(self, key):
        """Retrieves additional data from the state
        """
        if self._data is None:
            return None
        if key in self._data:
          return self._data[key]
        return None
        
    def __str__(self):
        """Return a string representation of this State
        """
        strs = self.getName()
        # initial?
        if self._initial:
            strs += ", Initial State"
        # final? 
        if self._final:
            strs += ", Final State"
        strs += "\n"        
        # outTransitions
        for t in self._outTrans:
            strs += "%s" % t            
        # inTransitions
        for t in self._inTrans:
            strs += "%s" % t 
            
        return strs
        
###############################################################################

class Transition:
    """Class Transition
    """        
    def __init__(self, pred, succ, label):
        """Initialize a transition
        """
        self._label = label
        self._pred  = None # predecessor state 
        self._succ  = None # successor state
        self.setPred(pred)
        self.setSucc(succ)

    def setPred(self, pred):
        """Set predecessor state of the transition
        """
        if isinstance(pred, State):
            self._pred = pred
        else:
            raise StateError("not a State")
        
    def setSucc(self, succ):
        """Set successor state of the transition
        """
        if isinstance(succ, State):
            self._succ = succ
        else:
            raise StateError("not a State") 
    
    def getLabel(self):
        """Return label of the transition
        """
        return self._label
        
    def getPred(self):
        """Return predecessor state
        """
        return self._pred
    
    def getSucc(self):
        """Return successor state
        """
        return self._succ
               
    def __str__(self):
        """Return string 
        """
        return self._pred.getName() +","+ self._succ.getName() +","+ self.getLabel() +"\n"
        
###############################################################################        
    
class Automaton(object):
    """Abstract Automaton Class
    """
    def __init__(self, alphabet):
        """Empty automaton
        """
        self._initials   = list()
        self._stateIndex = dict()
        self._finalIndex = dict()
        self._alphabet   = tuple(alphabet)
                
    def __len__(self):
        """Return number of states 
        """
        return len(list(self._stateIndex.keys()))
    
    def addState(self, name=None, final=False, initial=False):
        """Abstract method
        """
        raise AutomatonError("Not implemented")
    
    def addTransition(self, source, target, label):
        """Abstract method
        """
        raise AutomatonError("Not implemented")

    def getAlphabet(self):
        """Return _alphabet
        """
        return self._alphabet    
        
    def getInitials(self):
        """Return initial states
        """
        return self._initials 
    
    def getFinals(self):
        """Return final states
        """
        return list(self._finalIndex.values())    
   
    def getNumberStates(self):
        return len(list(self._stateIndex.values()))


    def getStates(self):
        """Return states
        """
        return list(self._stateIndex.values()) 
    
    def getState(self, name):
        """
        Return the state with name given
        Return None if not exist
        """
        if (name in list(self._stateIndex.keys())):
            return self._stateIndex[name]
        else:
            return None    
    
    def readFsa(self, fsaFile):
        """construct a FSA from file
        """
        handle = open(fsaFile, 'r')
        lines = handle.readlines()
        handle.close()

        prefix = 'u'

        # Initial state names
        iStateNames = lines[0].rstrip("!\n").split(",")
        for iStateName in iStateNames:
            self.addState(prefix+iStateName, initial=True)
            
        # Transitions
        for i in range(1, (len(lines)-1)):
            prod = lines[i].rstrip("!\n").split(",")
            #print "%s,%s,%s" % (prod[0], prod[1], prod[2])
            self.addTransition(prefix+prod[0], prefix+prod[1], prod[2])
                
        # Final states
        fStateNames = lines[-1].lstrip("!").rstrip("\n").split(",")
        for fStateName in fStateNames:
            self.addState(prefix+fStateName, final=True)
 
    def __str__(self):
        """Return a verbose string representation of this FSA
        """
        strs = "Initials: " 
        for initial in self._initials:
            strs += initial.getName() + ","
        strs += "\n"
        
        for stat in list(self._stateIndex.values()):
            for trans in stat.getOutTransition():
                strs += "%s" % trans 
        
        strs += "Finals: "
        for final in list(self._finalIndex.values()):
            strs += final.getName() + ","
        
        return strs
       
    def isDFA(self):
        """Check if a DFA
        """
        # deterministic 
        for state in list(self._stateIndex.values()):
            outLabels = []
            for trans in state.getOutTransition():
                label = trans.getLabel() 
                if label in outLabels:
                    return False
                outLabels.append(label)
        
        return True              
       
############################################################################### 

class NFA(Automaton):    
    """Nondeterministic finite automaton
    """       
    def addState(self, name=None, final=False, initial=False):
        """
        Add one state to Automaton if not exist
        Return the state
        """
        if name is None:
            raise StateError("not named state")
        
        s = self.getState(name)
        if s == None:
            s = State(name, final, initial)
            self._stateIndex[name] = s     # add to state set
        
        # Add to initial and final    
        if final:
            self.getState(name).setFinal(True)
            self._finalIndex[name] = s
                
        if initial:
            self.getState(name).setInitial(True)
            self._initials.append(s)
                        
        return self.getState(name)

    def addTransition(self, predName, succName, label):
        """Add a transition, add State(s) if not exist
        """
        pred = self.addState(predName)
        succ = self.addState(succName)
        if label not in self._alphabet:
            raise AutomatonError("Label not in Alphabet")
        
        t = Transition(pred, succ, label)
        
        pred.addOutTransition(t)
        succ.addInTransition(t)                         
            
############################################################################### 

class DFA(Automaton):    
    """Deterministic finite automaton
    """   
    def addState(self, name=None, final=False, initial=False):
        """
        Add one state to Automaton if not exist
        Raise exception if more than one initial state exists
        Return the state
        """
        if name is None:
            raise StateError("not named state")

        s = self.getState(name)
        if s == None:
            s = State(name, final, initial)
            self._stateIndex[name] = s     # add to state set
                    
        # verifying only one initial state
        if initial:                    
            if len(self._initials) == 1:
                raise DFAError("only one initial state allowed")
            else:
                self.getState(name).setInitial(True)
                self._initials.append(s)

        if final:
            self.getState(name).setFinal(True)           
            self._finalIndex[name] = s # add to final state set
                        
        return self.getState(name)

    def addTransition(self, predName, succName, label):
        """
        Add a transition, add State(s) if not exist
        Raise exception if more than one outTransition for predecessor state
        """
        pred = self.addState(predName)
        succ = self.addState(succName)
        t = Transition(pred, succ, label)
        
        # verifying only one outTransition exist for pred
        if len(pred.getOutTransition(label)) == 1:
            raise DFAError("only one out transition allowed")
        else:
            pred.addOutTransition(t)
        succ.addInTransition(t)     


###############################################################################
            
